package j2024.j202408;

import java.util.Scanner;

public class j0822 {
    public static void main1(String[] args) {
        Scanner in =new Scanner(System.in);
        int n  = in.nextInt(),V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        int[][] dp = new int[n+1][V+1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();w[i] = in.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=v[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= V; i++) {
            dp[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=v[i] && dp[i][j-v[i]]!=-1){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[n][V]==-1?0:dp[n][V]);
    }
    public static void main2(String[] args) {
        Scanner in =new Scanner(System.in);
        int n  = in.nextInt(),V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        int[] dp = new int[V+1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();w[i] = in.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <=V; j++) {
               dp[j]  =Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);
            for (int j = 0; j <= V; j++) {
                dp[j] = 0;
            }
        for (int i = 1; i <= V; i++) {
            dp[i] = -0x3f3f3f3f;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <=V; j++) {
                dp[j]  =Math.max(dp[j],dp[j-v[i]]+w[i]);

            }
        }
        System.out.println(dp[V]<0?0:dp[V]);
    }

    /**
     * 322. 零钱兑换
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp =new int[n+1][amount+1];
        for (int i = 1; i <= amount; i++) {
            dp[0][i] = 0x3f3f3f3f;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1]){
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[n][amount]>=0x3f3f3f3f?-1:dp[n][amount];
    }

    /**
     * 518. 零钱兑换 II
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int x:coins){
            for (int i = x; i <= amount; i++) {
                dp[i]+=dp[i-x];
            }
        }
        return dp[amount];
    }

    /**
     * 279. 完全平方数
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1]+1;
            for (int j = 2; j*j <= i; j++) {
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
